Crate bbs_plus

Implements BBS and BBS+ signatures.

BBS+ signature according to the paper: Anonymous Attestation Using the Strong Diffie Hellman Assumption Revisited. Provides

• signature creation and verification with signature in group G1 and public key in group G2 and vice-versa.
• proof of knowledge of signature and corresponding messages in group G1 as that is more efficient.

BBS signature according to the paper: Revisiting BBS Signatures. Provides

• signature creation and verification with signature in group G1 and public key in group G2.
• proof of knowledge of signature and corresponding messages. The implemented protocols are a bit different from whats mentioned in the paper. The modifications are made in the Schnorr proof part to allow for use-cases like proving equality (in zero-knowledge) of messages among same/different signatures or proving predicates (in zero-knowledge) about messages. Check the documentation of corresponding modules for more details.

Threshold BBS and BBS+ signatures based on the paper Threshold BBS+ Signatures for Distributed Anonymous Credential Issuance The threshold signing protocol has 3 phases (not communication rounds) 1. This is the randomness generation phase 2. This is the phase where multiplications happen 3. Here the outputs of phases 1 and 2 and the messages to be signed are used to generate the signature.

Note that only 3rd phase requires the messages to be known so the first 2 phases can be treated as pre-computation and can be done proactively. Secondly since the communication time among signers is most likely to be the bottleneck in threshold signing, phase 1 and 2 support batching meaning that to generate n signatures only a single execution of phase 1 and 2 needs to done, although with larger inputs. Then n executions of phase 3 are done to generate the signature. Also, its assumed that parties have done the DKG as well as the base OT and stored their results. Both BBS and BBS+ implementations share the same multiplication phase and the base OT phase but their phase 1 is slightly different.

Modules

1. BBS and BBS+ signature parameters and key generation module - setup. The signature params for BBS are slightly different from BBS+ but public key is same.
2. BBS+ signature module - signature
3. BBS+ proof of knowledge of signature module - proof
4. BBS signature module - signature_23
5. BBS proof of knowledge of signature module - proof_23
6. BBS proof of knowledge of signature module, alternate implementation - proof_23_cdl
7. Threshold BBS and BBS+ signatures - threshold

The implementation tries to use the same variable names as the paper and thus violate Rust’s naming conventions at places.

Modules

• error
• prelude
• proof
  Proof of knowledge of BBS+ signature and corresponding messages as per section 4.5 of the BBS+ paper
• proof_23
  Proof of knowledge of BBS signature and corresponding messages as per section 5.2 of the BBS paper with slight modification described below. The paper requires the prover to prove e(A_bar, X_2) = e (B_bar, g2) where B_bar = C(m)*r + A_bar*-e. The prover sends A_bar, B_bar to the verifier and also proves the knowledge of r, e and any messages in C(m) in B_bar. Here r is a random element chosen by the prover on each proof of knowledge. Above approach has a problem when some messages under 2 signatures need to be proven equal in zero knowledge. Because r will be different for each signature, the witnesses for the Schnorr proof will be different, i.e. m*r and m*r' for the same message m and thus the folklore method of proving equal witnesses in multiple statements cant be used. Thus the protocol below accepts r (called signature randomizer) from the prover who can use the same r when proving message equality in multiple signatures. When doing so also prove the equality of r in term C_j(m) * r and thus use the same blinding eg. when proving equality of certain messages under 2 signatures sigma_1 = (A_1, e_1) and sigma_2 = A_2 * e_2, it should be proven that r and Schnorr responses for the equal messages m_k are equal. i.e. for known messages J_1, J_2, hidden messages I_1, I_2 for signatures sigma_1, sigma_2 with equal messages m_k being a subset of I_1, I_2, r and m_k are same in following 2 relations: {B_1}_bar = C_{J_1}(m) * r + \sum_{i in I_1}(h_i * (m_i*r)) + {A_1}_bar * -e_1 {B_2}_bar = C_{J_2}(m) * r + \sum_{i in I_2}(h_i * (m_i*r)) + {A_2}_bar * -e_2 Its important to prove that r is same in C_{J_1}(m) and C_{J_2}(m) otherwise two unequal messages m_a and m_b can be proven equal by using signature randomizers r_1 and r2 such that m_a * r_1 = m_b * r_2
• proof_23_cdl
  Proof of knowledge of BBS signature and corresponding messages as per section 5.2 of the BBS paper with slight modification described below. The paper requires the prover to prove e(A_bar, X_2) = e (B_bar, g2) where A_bar = A * r and B_bar = C(m)*r + A_bar*-e. The prover sends A_bar, B_bar to the verifier and also proves the knowledge of r, e and any messages in C(m) in B_bar. Here r is a random element chosen by the prover on each proof of knowledge. Above approach has a problem when some messages under 2 signatures need to be proven equal in zero knowledge or proving predicates about the messages in zero-knowledge using LegoSnark where the proof contains a Pedersen commitment to witness of the SNARK. Because r will be different for each signature, the witnesses for the Schnorr proof will be different, i.e. m*r and m*r' for the same message m and thus the folklore method of proving equal witnesses in multiple statements cant be used. Thus the protocol below uses a similar approach as used in BBS+. The prover in addition to sending A_bar = A*r1*r2, B_bar = (C(m) - A*e)*r1*r2 to the verifier sends d = C(m)*r2 as well for random r1, r2. The prover calculates r3 = 1 / r2 and creates 2 Schnorr proofs for:
• setup
  Keys and setup parameters
• signature
  BBS+ signature and verification as per section 4.3 of the paper
• signature_23
  BBS signature and verification. Signature is in group G1.
• threshold
  Implementation of threshold BBS and BBS+ based on the paper Threshold BBS+ Signatures for Distributed Anonymous Credential Issuance The threshold signing protocol has 3 phases (not communication rounds) 1. This is the randomness generation phase 2. This is the phase where multiplications happen 3. Here the outputs of phases 1 and 2 and the messages to be signed are used to generate the signature.